"""
遍历策略+判断条件=搜索算法
证明从略, 认为定能遍历所有元素
BFS简介 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，
这一算法也是很多重要的图的算法的原型。 其别名又叫 BFS ，属于一种盲目搜寻法，
目的是系统地展开并检查图中的所有节点，以找寻结果。
"""

def BFS(start,graph):
    queue =[]
    visit = []
    queue.append(start)
    visit.append(start)
    while queue:
        node = queue.pop(0)
        nodes = graph[node]
        for i in nodes:
            if i not in visit:
                queue.append(i)
                visit.append(i)
        # print(node,end='\t')
    return visit

def DFS(start,graph):
    stack = []
    visit = []
    stack.append(start)
    visit.append(start)
    while stack:
        node = stack.pop()
        nodes = graph[node]
        for i in nodes:
            if i not in visit:
                stack.append(i)
                visit.append(i)
        # print(node,end='\t')
    return visit

if __name__ == "__main__":
    graph = {
        'A' : ['B','C','D'],
        'B' : ['A','E','F'],
        'C' : ['A','D','F','G'],
        'D' : ['A','C','G'],
        'E' : ['B'],
        'F' : ['B','C'],
        'G' : ['C','D']
    }

    visit = BFS('A',graph)
    print(visit)

    visit = DFS('A',graph)
    print(visit)